//  给定一棵二叉搜索树的根节点root
//  要求将这棵二叉树转换为一个已排序的双向循环链表，要求不能创建新的节点，只能调整树中节点指针的指向

// 思路：中序遍历，是有序的，更改指针
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，递归栈的大小

function treeToDoublyList(root) {
    if (!root) {
        return null
    }
    let head = null
    let tail = null
    function dfs(root) {
        if (!root) {
            return null
        }
        dfs(root.left)
        if (!head) {
            head = root
        } else {
            tail.right = root
            root.left = tail
        }
        tail = root
        dfs(root.right)
    }
    dfs(root)
    tail.right = head
    head.left = tail
    return head
}

const root = {
    val: 4,
    left: {
        val: 3,
        left: {
            val: 2,
        },
        right: {
            val: 3.5,
        },
    },
    right: {
        val: 6,
    },
};

console.log(treeToDoubleList(root))